#include <stdio.h>


void printArray(int** priceArray,int n)
{
    for(int j=0;j<n;j++)
    {
        for(int i=0;i<n-j;i++)
        {
            printf("%d\t",priceArray[i][j]);
        }
        printf("\n");
    }
    printf("\n");

}

void printArray2(unsigned int** priceArray,int n)
{
    for(int j=0;j<n;j++)
    {
        for(int i=0;i<n-j;i++)
        {
            printf("%u\t",priceArray[i][j]);
        }
        printf("\n");
    }
    printf("\n");

}

int main(){
    int n;
    scanf("%d",&n);
    unsigned  int* score=new unsigned int[n];

    //第i j列代表以i为起点数j+1个的最大得分
    unsigned int** scoreDp=new unsigned int*[n];
    //第i j列代表以i为起点数j+1个的最大得分的中点位置
    int** centerDp=new int*[n];

    int i,j,k;
    for(i=0;i<n;i++)
    {
        scanf("%d",&score[i]);

        scoreDp[i]=new unsigned int[n];
        centerDp[i]=new int[n];
        for(j=0;j<n;j++)
        {
            scoreDp[i][j]=0;
            centerDp[i][j]=-1;
        }
    }

    for(j=0;j<n;j++)
    {
        for(i=0;i<n-j;i++)
        {
            if(j==0)
            {
                scoreDp[i][j]=score[i];
                centerDp[i][j]=i;
            }
            else if(j==1){
                scoreDp[i][j]=score[i]+score[i+1];
                centerDp[i][j]=i;
            }
            else{
                unsigned int max=0;
                int maxIndex=-1;
                for(k=0;k<=j;k++)
                {
                    int centerIndex=i+k;
                    unsigned int left=1;
                    
                    if(k>0)
                    {
                        left=scoreDp[i][k-1];
                    }

                    unsigned int right=1;
                    int right_st=centerIndex+1;
                    int right_j=j-k;
                    if(right_j>0)
                    {
                        right=scoreDp[right_st][right_j-1];
                    }

                    unsigned int value=right*left+score[centerIndex];
                    if(value>max)
                    {
                        max=value;
                        maxIndex=centerIndex;
                    }
                }

                scoreDp[i][j]=max;
                centerDp[i][j]=maxIndex;
            }
        }
    }

    // printArray2(scoreDp,n);
    // printArray(centerDp,n);

    printf("%u\n",scoreDp[0][n-1]);
    int* start=new int[n];
    int* end=new int[n];

    start[0]=0;
    end[0]=n-1;
    int len=1;

    while (len>0)
    {
        //出栈
        int s=start[len-1];
        int e=end[len-1];
        len--;


        int center=centerDp[s][e];
        printf("%d ",center+1);

        //右边入栈
        if(e>0)
        {
            start[len]=center+1;
            end[len]=e+s-center-1;
            len++;
        }

        //左边入栈
        if(center>s)
        {
            start[len]=s;
            end[len]=center-1-s;
            len++;
        }
    }

    printf("\n");
    
    
    delete score;
    for(i=0;i<n;i++)
    {
        delete scoreDp[i];
        delete centerDp[i];
    }
    delete scoreDp;
    delete centerDp;

    delete start;
    delete end;
    return 0;
}